/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-15 09:12:53
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-15 09:12:58
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法40.N字形变换(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/zigzag-conversion
 */
class Solution {
public:
    // 模拟优化,找规律
    // 第一行,0,0+d,0+2d...0+kd
    // 第k行,(k,d-k),(k+d,d-k+d)...(k+2d,d-k+2d)
    // 最后一行,n-1,n-1+d,n-1+2d...n-1+kd
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        string ret;
        int d = 2 * numRows - 2, n = s.size(); // 公差d
        // 先处理第一行
        for(int i = 0; i < n; i += d) ret += s[i];
        // 处理中间行
        for(int k = 1; k < numRows - 1; k++) { // 枚举每一行
            for(int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if(i < n) ret += s[i];
                if(j < n) ret += s[j]; 
            }
        } 
        // 处理最后一行
        for(int i = numRows - 1; i < n; i += d) ret += s[i];
        return ret;
    }
};